Easy2Siksha.com
GNDU QUESTION PAPERS 2023
BA/BSc 4
th
SEMESTER
COMPUTER SCIENCE
(Data Structures & Programming Language Using C++)
Time Allowed: 3 Hours Maximum Marks: 75
Note: Aempt Five quesons in all, selecng at least One queson from each secon. The
Fih queson may be aempted from any secon. All quesons carry equal marks.
SECTION-A
1. What is an algorithm? What are its features? Explain all types of asymptoc notaons
and importance of each notaon. Also explain why it is much desirable to reduce me
completely than space complexity of an algorithm. Prove that the funcon f(x) = 5x4 + 7x
+3 is 0 (x¹). 15
2. (a) How are one-dimensional, two-dimensional and three-dimensional arrays inialized
and represented in main memory? Explain with example program.
(b) Write an algorithm for the creaon, inseron and deleon of elements from a doubly
Linked List.
SECTION-B
3. (a) List the applicaons of Stack. Write an algorithm for converng Parenthesized Inx
expression into Posix expression.
Easy2Siksha.com
b) Given the following sequence of leers and asterisks: EAS*Y*QUE**ST*IO*N*, Consider
the stack data structure, supporng two operaons push and pop. Suppose that for the
above sequence, each leer (such as E) corresponds to a push of that leer onto the stack
and each asterisk () corresponds to a pop operaon on the stack. Show the sequence of
values returned by the pop operaons.
4. What are Circular Queue and Priority Queue? Write an algorithm to insert and delete an
element from a Circular Queue.
SECTION-C
5. Write an algorithm for Quick Sort. Sort the sequence of numbers 15, 10, 13, 9, 12, 7
using Quick Sort. Analyze the me complexity of Quick Sort in best and worst cases.
6. Why Binary Search algorithm is more ecient than linear search? Depict your answer
with suitable example. Write recursive binary search algorithm and analyze its complexity
in worst case.
SECTION-D
7. (a) Briey explain the features of C++ programming language. Explain dierent
mechanism for accessing data members and member funcons in a class with examples.
(b) List the dierent types of constructors. Write a program to illustrate the use of
dierent types of constructors.
8. (a) List the rules associated with operator overloading. What are the operators that
cannot be overloaded? Write a program to overload any one of the binary operators.
(b) Write a C++ program to illustrate the process of mul-level mulple inheritance
concept of C++ language.
Easy2Siksha.com
GNDU ANSWER PAPERS 2023
BA/BSc 4
th
SEMESTER
COMPUTER SCIENCE
(Data Structures & Programming Language Using C++)
Time Allowed: 3 Hours Maximum Marks: 75
Note: Aempt Five quesons in all, selecng at least One queson from each secon. The
Fih queson may be aempted from any secon. All quesons carry equal marks.
SECTION-A
1. What is an algorithm? What are its features? Explain all types of asymptoc notaons
and importance of each notaon. Also explain why it is much desirable to reduce me
completely than space complexity of an algorithm. Prove that the funcon f(x) = 5x4 + 7x
+3 is 0 (x¹). 15
Ans: What is an Algorithm?
Imagine you want to make tea. You don’t just randomly pour things. You follow steps:
1. Boil water
2. Add tea leaves
3. Add milk and sugar
4. Stir
5. Serve
This step-by-step process is nothing but an algorithm.
In computer science, an algorithm is a set of finite, step-by-step instructions designed to
solve a specific problem. Just like a recipe gives steps to cook food, an algorithm gives steps
to solve tasks like sorting numbers, searching names, or performing calculations.
Easy2Siksha.com
Features of a Good Algorithm
A good algorithm is not just any set of steps; it has special qualities:
1. Well-defined Input
There should be clear input values. For example, if you are sorting numbers, the input
should be a list of numbers.
2. Well-defined Output
Every algorithm must produce useful output. Sorting algorithm outputs sorted numbers.
3. Finite Steps
It should not run forever. It must finish after a certain number of steps.
4. Definiteness (Clarity)
Each step should be very clear, with no confusion. No vague instructions like “Do it
somehow”.
5. Effectiveness
Each instruction must be simple enough to be executed easily by a computer.
6. Generality
One algorithm should work for a wide range of inputs, not just one specific case.
When an algorithm has these properties, we call it efficient and reliable.
What is Time and Space Complexity?
Now imagine you have two teachers checking exam papers.
• Teacher A checks very fast but needs many assistants (more resources).
• Teacher B checks slowly but works alone (less resources).
Similarly, when we evaluate an algorithm, we judge it based on:
Time Complexity
How fast the algorithm runs.
It measures time taken w.r.t. input size.
Easy2Siksha.com
Space Complexity
How much memory the algorithm uses.
In real life:
• Users care more about speed.
• Computers today have large memory.
So, reducing time is usually more important than reducing space.
This is why programmers say:
“Time is precious. Space is manageable.”
Though space matters, saving time improves user experience, performance, and efficiency.
Asymptotic Notations
Now comes the mathematical superhero part!
Asymptotic notations help us compare algorithms scientifically. Instead of saying:
“This algorithm is fast” or “This one is slow”,
we express growth mathematically.
They tell us how an algorithm behaves when input size becomes very large.
There are mainly three asymptotic notations.
Big-O Notation – Upper Bound (Worst Case)
Big-O tells the maximum time an algorithm might take.
Think of it like:
“Even in the worst possible situation, it won’t be slower than this.”
Example:
Searching for a number in an unsorted list may require checking every element.
So worst case = checking n elements
Therefore:
O(n)
Easy2Siksha.com
This helps developers guarantee performance.
Omega (Ω) Notation – Lower Bound (Best Case)
This tells the minimum time the algorithm will take.
Think:
“In the best possible situation, performance will be at least this good.”
Example:
If the first element you check is the correct one, time = constant
So best case:
Ω(1)
It shows the most optimistic scenario.
Theta (Θ) Notation – Tight Bound (Average Case)
Theta tells the exact or average growth rate.
Think:
“This is the realistic expected performance.”
If time complexity is the same in best and worst range, then:
Θ(n)
Theta is like saying:
Not too much, not too little — exact idea.
Why Reducing Time is More Important Than Space?
Let’s relate to real life.
Suppose a website loads slowly.
Users get angry, leave, give bad reviews.
But if the website uses a bit more memory, nobody notices.
Easy2Siksha.com
Also:
• Memory is becoming cheaper and larger.
• Time can never be bought back.
• Faster tools = better productivity.
• In real world apps like Google, YouTube, Banking Systems — speed is everything.
Therefore,
Improving time complexity is usually more important than improving space complexity.
Proof that
f(x) = 5x⁴ + 7x + 3 is O(x⁴)
To prove Big-O mathematically,
we must show:
f(x) ≤ C × g(x)
for x ≥ k
Where g(x) is x⁴ here, because we are checking whether it belongs to O(x⁴)
So:
f(x) = 5x⁴ + 7x + 3
Now observe something important:
When x becomes very large,
x⁴ grows extremely fast compared to x and constants.
Meaning:
• 7x becomes very small in comparison
• 3 is negligible
• 5x⁴ dominates everything
So we can write:
5x⁴ + 7x + 3 ≤ 5x⁴ + x⁴ + x⁴ (for large x)
≤ 7x⁴
Easy2Siksha.com
So,
For x ≥ 1,
f(x) ≤ 7x⁴
Therefore,
We can take
C = 7
k = 1
So it satisfies the Big-O rule.
Thus,
f(x) = O(x⁴)
Meaning, the function grows no faster than x⁴.
Conclusion (Simple Summary Like a Story Ending)
Algorithms are like recipes that tell computers how to solve problems step by step. A good
algorithm must be clear, efficient, finite, and useful. To measure their performance, we use
time and space complexity.
Asymptotic notations help us compare algorithms scientifically:
• Big-O (O) → Worst case guarantee
• Omega (Ω) → Best case guarantee
• Theta (Θ) → Average/tight bound
Time is generally more important to optimize than space because speed affects user
experience and system efficiency more critically than memory usage.
Finally, the function 5x⁴ + 7x + 3 was proved to be O(x⁴) because x⁴ term dominates for large
inputs.
2. (a) How are one-dimensional, two-dimensional and three-dimensional arrays inialized
and represented in main memory? Explain with example program.
(b) Write an algorithm for the creaon, inseron and deleon of elements from a doubly
Linked List.
Ans: Part (a) Arrays: Initialization and Representation in Memory
What is an Array?
Easy2Siksha.com
An array is a collection of elements of the same data type stored in contiguous memory
locations. It allows us to access elements using an index.
Think of an array like a row of lockers in a school corridor. Each locker has a number
(index), and inside it, you can store a value.
1. One-Dimensional Array
• Initialization:
c
int arr[5] = {10, 20, 30, 40, 50};
Here, arr is a one-dimensional array of 5 integers.
• Memory Representation: Each element is stored in consecutive memory cells. If the
base address is 1000 and each integer takes 4 bytes, then:
o arr[0] → 1000
o arr[1] → 1004
o arr[2] → 1008
o arr[3] → 1012
o arr[4] → 1016
This is like lockers arranged in a straight line, each holding one value.
2. Two-Dimensional Array
• Initialization:
c
int matrix[2][3] = {
{1, 2, 3},
{4, 5, 6}
};
This is a 2x3 matrix.
• Memory Representation: Stored in row-major order (C language default). That
means the first row is stored completely, then the second row.
o matrix[0][0] → 1000
o matrix[0][1] → 1004
o matrix[0][2] → 1008
o matrix[1][0] → 1012
o matrix[1][1] → 1016
o matrix[1][2] → 1020
Easy2Siksha.com
Imagine lockers arranged in rows and columns, but in memory they are flattened row by
row.
3. Three-Dimensional Array
• Initialization:
c
int cube[2][2][3] = {
{
{1, 2, 3},
{4, 5, 6}
},
{
{7, 8, 9},
{10, 11, 12}
}
};
This is a 2x2x3 cube.
• Memory Representation: Stored in row-major order again. First, all elements of
cube[0][0], then cube[0][1], then cube[1][0], and so on.
Think of it like multiple pages of a notebook. Each page has rows and columns. In
memory, the pages are flattened one after another.
Example Program (C Language)
c
#include <stdio.h>
int main() {
int arr[5] = {10, 20, 30, 40, 50};
int matrix[2][3] = {{1, 2, 3}, {4, 5, 6}};
int cube[2][2][3] = {
{{1, 2, 3}, {4, 5, 6}},
{{7, 8, 9}, {10, 11, 12}}
};
printf("1D Array: %d\n", arr[2]); // Output: 30
printf("2D Array: %d\n", matrix[1][2]); // Output: 6
printf("3D Array: %d\n", cube[1][0][2]); // Output: 9
return 0;
}
This program shows how arrays are initialized and accessed.
Easy2Siksha.com
Part (b) Doubly Linked List
What is a Doubly Linked List?
A doubly linked list (DLL) is a sequence of nodes where each node has:
1. Data (the value stored).
2. Pointer to the next node.
3. Pointer to the previous node.
Imagine a train where each coach is connected to the next and also to the previous one.
You can move forward or backward easily.
Operations on Doubly Linked List
1. Creation of a DLL
Algorithm:
1. Start with an empty list (head = NULL).
2. Create a new node with data.
3. If the list is empty, set head = new node.
4. Otherwise, traverse to the end and attach the new node.
5. Update the next and prev pointers accordingly.
2. Insertion in DLL
There are three cases:
• At the Beginning:
1. Create a new node.
2. Set new node’s next = head.
3. Set head’s prev = new node.
4. Update head = new node.
• At the End:
1. Traverse to the last node.
2. Set last node’s next = new node.
3. Set new node’s prev = last node.
• At a Given Position:
1. Traverse to the desired position.
2. Adjust pointers of previous and next nodes to insert the new node.
3. Deletion in DLL
Again, three cases:
Easy2Siksha.com
• From the Beginning:
1. Set head = head->next.
2. Set head->prev = NULL.
3. Free the old head node.
• From the End:
1. Traverse to the last node.
2. Set last->prev->next = NULL.
3. Free the last node.
• From a Given Position:
1. Traverse to the node.
2. Adjust pointers of previous and next nodes to bypass the node.
3. Free the node.
Example Algorithm (Pseudocode)
text
Algorithm CreateDLL(data):
newNode ← allocate memory
newNode.data ← data
newNode.next ← NULL
newNode.prev ← NULL
if head = NULL then
head ← newNode
else
temp ← head
while temp.next ≠ NULL do
temp ← temp.next
temp.next ← newNode
newNode.prev ← temp
End Algorithm
text
Algorithm InsertAtBeginning(data):
newNode ← allocate memory
newNode.data ← data
newNode.next ← head
newNode.prev ← NULL
if head ≠ NULL then
head.prev ← newNode
head ← newNode
End Algorithm
text
Algorithm DeleteAtEnd():
if head = NULL then
print "List Empty"
else
Easy2Siksha.com
temp ← head
while temp.next ≠ NULL do
temp ← temp.next
temp.prev.next ← NULL
free(temp)
End Algorithm
Why Are These Concepts Important?
• Arrays: Efficient for indexing and storing data in contiguous memory. Best for fixed-
size collections.
• Doubly Linked Lists: Flexible, allow dynamic memory usage, and easy
insertion/deletion at both ends.
Arrays are like fixed lockers in a corridor, while linked lists are like train coaches that can
be added or removed anytime.
Final Thoughts
The question beautifully combines static and dynamic data structures. Arrays show how
data is stored in memory in a structured way, while doubly linked lists show how data can
be managed dynamically with flexibility.
SECTION-B
3. (a) List the applicaons of Stack. Write an algorithm for converng Parenthesized Inx
expression into Posix expression.
b) Given the following sequence of leers and asterisks: EAS*Y*QUE**ST*IO*N*, Consider
the stack data structure, supporng two operaons push and pop. Suppose that for the
above sequence, each leer (such as E) corresponds to a push of that leer onto the stack
and each asterisk () corresponds to a pop operaon on the stack. Show the sequence of
values returned by the pop operaons.
Ans: What is a Stack? (In Simple Language)
Imagine plates in your kitchen. You keep plates one on top of another. When you want a
plate, you always take the top plate first. This is exactly how a stack works.
So stack follows:
LIFO – Last In, First Out
Whatever goes last, comes out first.
Easy2Siksha.com
Applications of Stack (Where is Stack Used in Real Life & Computers?)
Stacks are not only theory — they are very useful in the real world and computer science.
Here are the most important applications explained simply:
Expression Evaluation
When we evaluate mathematical expressions like:
( A + B ) * C
Computers internally use stacks to understand precedence and parentheses. Without
stacks, expressions would confuse computers!
Expression Conversion (Infix → Postfix / Prefix)
Computers cannot easily understand expressions like:
A + B
But they easily understand:
AB+
So stacks help convert Infix expressions to Postfix or Prefix.
This is exactly what your question asks later.
Function Calls / Recursion
Whenever a program calls a function, stack stores:
• Function return address
• Local variables
• Parameters
When the function ends, stack removes it.
This is why we have Stack Overflow errors when too many functions call each other!
Undo / Redo in Apps
Easy2Siksha.com
Have you ever pressed Undo (Ctrl + Z)?
Every action is stored on a stack.
Undo simply pops the last change.
Backtracking
Games like maze solving, puzzle solving, etc., use stacks to remember previous positions.
Browser History
When you open pages:
Google → YouTube → Instagram
Back button uses stack to go back step by step.
So, stack is like memory brain of a computer that remembers things in reverse order.
Algorithm: Converting Parenthesized INFIX to POSTFIX
Let us first understand the terms clearly:
• Infix Expression: Operator in middle
Example: A + B
• Postfix Expression: Operator after operands
Example: AB+
Computers prefer Postfix because:
• No need of parentheses
• Evaluation becomes easy
• Clear priority
Basic Idea of Algorithm
We scan expression from left to right,
We use a stack for operators,
Operands (A, B, C…) directly go to output.
Easy2Siksha.com
Simple Rules
If character is operand → Send to output
If character is operator → Push into stack, but:
• Pop operators with higher or equal precedence
If ( appears → Push it
If ) appears → Pop until ( comes
At end → Pop all remaining operators
Example to Feel the Algorithm
Expression:
(A + B) * C
Step-by-step:
• Read ( → push
• Read A → output: A
• Read + → push
• Read B → output: AB
• Read ) → pop until ( → output becomes: AB+
• Read * → push *
• Read C → output: AB+C
End → pop remaining *
Final answer:
AB+C*
This is Postfix!
So that's how the algorithm works using stacks.
Part (b): POP Sequence Problem
We are given:
E A S * Y * Q U E * * S T * I O * N *
Easy2Siksha.com
Meaning:
• Every letter = PUSH into stack
• Every * = POP from stack and record the popped element
Let us simulate it like a real stack.
Step-by-step Simulation
Action
Operation
Stack Status
Output (when POP happens)
E
Push E
[E]
—
A
Push A
[E, A]
—
S
Push S
[E, A, S]
—
*
Pop
[E, A]
S
Y
Push Y
[E, A, Y]
—
*
Pop
[E, A]
Y
Q
Push Q
[E, A, Q]
—
U
Push U
[E, A, Q, U]
—
E
Push E
[E, A, Q, U, E]
—
*
Pop
[E, A, Q, U]
E
*
Pop
[E, A, Q]
U
S
Push S
[E, A, Q, S]
—
T
Push T
[E, A, Q, S, T]
—
*
Pop
[E, A, Q, S]
T
I
Push I
[E, A, Q, S, I]
—
O
Push O
[E, A, Q, S, I, O]
—
*
Pop
[E, A, Q, S, I]
O
N
Push N
[E, A, Q, S, I, N]
—
*
Pop
[E, A, Q, S, I]
N
Final Pop Output Sequence
The letters that came out from pop operations are:
S, Y, E, U, T, O, N
This is the required answer.
Final Simple Summary
• Stack works like a pile of plates.
• It follows Last In First Out (LIFO).
Easy2Siksha.com
• Stacks are used in expression evaluation, conversion, recursion, undo, browser
history, and many more.
• Infix to Postfix conversion uses stack to manage operator precedence and
parentheses.
• In the given push/pop question, every star means pop, and we traced outputs step-
by-step to get:
S Y E U T O N
4. What are Circular Queue and Priority Queue? Write an algorithm to insert and delete an
element from a Circular Queue.
Ans: Data structures are the backbone of computer science. Among them, queues are
particularly important because they model real-world scenarios like waiting lines, scheduling
tasks, or managing resources. This question asks us to explore two special types of queues—
Circular Queue and Priority Queue—and then write algorithms for insertion and deletion in
a Circular Queue. Let’s break it down step by step in a clear, engaging way.
What is a Queue?
A queue is a linear data structure that follows the FIFO (First In, First Out) principle.
Imagine people standing in line at a ticket counter: the first person to arrive is the first to be
served.
Circular Queue
Definition
A Circular Queue is a variation of the linear queue in which the last position is connected
back to the first position, forming a circle.
Think of it like chairs arranged in a circle for a game of musical chairs. After the last
chair, you come back to the first one.
Why Circular Queue?
• In a simple linear queue, once the rear reaches the end of the array, no more
elements can be inserted—even if there is free space at the front (due to deletions).
• Circular queues solve this problem by reusing empty spaces, making them more
efficient.
Representation
• Front pointer: Points to the first element.
• Rear pointer: Points to the last element.
• Both pointers move circularly using the formula:
Easy2Siksha.com
(index + 1) mod size
Priority Queue
Definition
A Priority Queue is a special type of queue where each element is associated with a priority.
Elements with higher priority are served before those with lower priority.
Imagine an emergency room in a hospital: patients are treated not in the order they
arrive, but based on the severity of their condition.
Characteristics
• Elements are dequeued based on priority, not just arrival order.
• If two elements have the same priority, they follow FIFO order.
• Implemented using arrays, linked lists, or heaps.
Algorithms for Circular Queue
Now let’s focus on the Circular Queue and write algorithms for insertion and deletion.
1. Insertion (Enqueue)
Algorithm:
Code
Algorithm Enqueue(CircularQueue, element):
1. If ( (rear + 1) mod size ) = front:
Print "Queue Overflow" (Queue is full)
2. Else if (front = -1 and rear = -1):
front ← 0
rear ← 0
queue[rear] ← element
3. Else:
rear ← (rear + 1) mod size
queue[rear] ← element
End Algorithm
Explanation:
• If the next position of rear equals front, the queue is full.
• If the queue is empty, initialize both front and rear to 0.
• Otherwise, move rear circularly and insert the element.
2. Deletion (Dequeue)
Easy2Siksha.com
Algorithm:
Code
Algorithm Dequeue(CircularQueue):
1. If (front = -1):
Print "Queue Underflow" (Queue is empty)
2. Else if (front = rear):
element ← queue[front]
front ← -1
rear ← -1
Return element
3. Else:
element ← queue[front]
front ← (front + 1) mod size
Return element
End Algorithm
Explanation:
• If front = -1, the queue is empty.
• If front = rear, only one element is left; after deletion, reset the queue.
• Otherwise, move front circularly and return the deleted element.
Example Walkthrough
Let’s take a Circular Queue of size 5.
• Initially: front = -1, rear = -1.
• Insert 10 → front = 0, rear = 0.
• Insert 20 → rear = 1.
• Insert 30 → rear = 2.
• Delete → removes 10, front = 1.
• Insert 40 → rear = 3.
• Insert 50 → rear = 4.
• Insert 60 → rear wraps around to 0 (circular movement).
This shows how the queue reuses empty spaces efficiently.
Real-Life Analogies
• Circular Queue: Like a rotating carousel—once you reach the last horse, you circle
back to the first.
• Priority Queue: Like airport boarding—priority passengers board first, regardless of
arrival time.
Summary Table
Easy2Siksha.com
Queue Type
Definition
Example
Circular
Queue
Queue where last connects to first, reusing
space
Musical chairs, carousel
Priority
Queue
Queue where elements are served by priority
Hospital emergency
room
Final Thoughts
Circular Queue and Priority Queue are powerful variations of the basic queue structure.
Circular Queue solves the problem of wasted space in linear queues by connecting the end
back to the beginning. Priority Queue changes the rules of service by focusing on
importance rather than arrival.
The algorithms for insertion and deletion in Circular Queue show how pointers move
circularly, ensuring efficient use of memory.
SECTION-C
5. Write an algorithm for Quick Sort. Sort the sequence of numbers 15, 10, 13, 9, 12, 7
using Quick Sort. Analyze the me complexity of Quick Sort in best and worst cases.
Ans: Understanding Quick
Imagine you are arranging books on a shelf. Instead of picking up every book and comparing
it with all others (like Bubble Sort or Selection Sort), you use a smarter way. You pick one
book as a reference and place all smaller books on one side and all larger books on the
other side. Then you repeat the same step for each side until everything is in order.
This is exactly how Quick Sort works.
It chooses one element called the pivot, rearranges the list so that elements smaller than
pivot move to its left and larger ones move to its right. Then it repeats the same process for
the left side and the right side until the whole list becomes sorted.
That’s why it is called Quick Sort – because in most cases, it actually works very fast.
Algorithm of Quick Sort (Simple Steps)
1. Select a pivot element
This can be first element, last element, middle element, or random element.
2. Partition the list
Rearrange the numbers so that:
o Elements smaller than pivot go to the left
o Elements greater than pivot go to the right
Now the pivot is in its correct sorted position.
Easy2Siksha.com
3. Recursively apply Quick Sort
o Apply Quick Sort to the left part
o Apply Quick Sort to the right part
4. Continue until single or no element remains (because a single element is already
sorted)
That’s it!
Short but powerful algorithm.
Now Let’s Sort
Sequence:
15, 10, 13, 9, 12, 7
Let’s assume first element as pivot.
Step 1
Pivot = 15
Compare all with pivot and arrange:
• Numbers smaller than 15 → left side: 10, 13, 9, 12, 7
• None are greater since 15 is largest
So arrangement becomes:
7, 10, 13, 9, 12 | 15
(Exact mechanism in real quick sort uses swapping, but idea remains same)
Now 15 is fixed at its final sorted position.
Now apply Quick Sort separately on left part:
10, 13, 9, 12, 7
Step 2
Sequence: 10, 13, 9, 12, 7
Pivot = 10
Separate:
Easy2Siksha.com
• Smaller than 10 → 9, 7
• Greater than 10 → 13, 12
So rearranged:
7, 9 | 10 | 13, 12
Now 10 is at correct position.
Now we sort two sides separately:
Left side: 7, 9
Right side: 13, 12
Step 3
Sort 7, 9
Pivot = 7
Smaller? none
Greater → 9
So:
7 | 9
Both are sorted.
Step 4
Sort 13, 12
Pivot = 13
Smaller → 12
Greater → none
So:
12 | 13
Sorted.
Final Sorted Sequence
Now collecting all sorted parts:
Easy2Siksha.com
7, 9, 10, 12, 13, 15
Your sorted output is:
7, 9, 10, 12, 13, 15
This is how Quick Sort rearranges and sorts efficiently.
Time Complexity Analysis
Quick Sort can behave differently depending on how well the pivot is chosen.
Best Case Time Complexity – O(n log n)
The best case happens when the pivot divides the list into two equal halves every time.
For example, pivot becomes middle value each time like:
half elements | pivot | half elements
This means:
• You divide list in half
• Then divide again
• Then again
This division continues like a tree structure.
Height of such tree = log n
Total work done = n log n
So,
Best Case Time Complexity = O(n log n)
This is why Quick Sort is loved and widely used in real-world applications.
Worst Case Time Complexity – O(n²)
Worst case happens when pivot selection is poor.
Example:
If array is already sorted and you always pick first element as pivot:
Easy2Siksha.com
1 , 2 , 3 , 4 , 5
pivot = 1
All elements go to right side.
So instead of dividing, you reduce only one element each time.
This makes list like:
n + (n-1) + (n-2) + ... + 1 = n²
So,
Worst Case Time Complexity = O(n²)
This generally happens when:
• Array already sorted
• Array reverse sorted
• Pivot chosen badly (first or last blindly)
Average Case Time Complexity – O(n log n)
In normal random situations, Quick Sort behaves very efficiently.
So:
Average Case = O(n log n)
This is why programmers and computers still prefer Quick Sort in many systems including
databases, sorting libraries, and programming languages.
Why Quick Sort is Still Popular?
Even though worst case seems bad, Quick Sort is still one of the fastest sorting methods
because:
✔ Uses Divide & Conquer
✔ Very fast on average
✔ Efficient in memory
✔ Used in real life programming languages (C, C++, Java, Python internally in some cases)
Only when stability is needed or worst case must be avoided, Merge Sort is preferred.
Easy2Siksha.com
Final Summary (
Quick Sort picks a pivot
Places smaller values left, larger values right
Repeats same process recursively
Final list becomes sorted
Sorted sequence of:
15, 10, 13, 9, 12, 7
Output: 7, 9, 10, 12, 13, 15
Time Complexity:
• Best Case → O(n log n)
• Average Case → O(n log n)
• Worst Case → O(n²)
6. Why Binary Search algorithm is more ecient than linear search? Depict your answer
with suitable example. Write recursive binary search algorithm and analyze its complexity
in worst case.
Ans: Linear Search
Definition
Linear Search is the simplest search technique. You start at the first element of the list and
check each element one by one until you find the target or reach the end.
Imagine you’re looking for a friend in a queue. You check each person in order until you
find your friend.
Example
Suppose we have an array:
Code
[5, 12, 18, 23, 45, 67, 89]
Searching for 45 using Linear Search:
• Compare with 5 → not equal
• Compare with 12 → not equal
• Compare with 18 → not equal
• Compare with 23 → not equal
Easy2Siksha.com
• Compare with 45 → found!
It took 5 comparisons to find the element.
Binary Search
Definition
Binary Search is a faster technique but requires the list to be sorted. Instead of checking
each element, it repeatedly divides the list into halves:
1. Compare the target with the middle element.
2. If equal → found.
3. If smaller → search the left half.
4. If larger → search the right half.
Imagine looking for a word in a dictionary. You don’t start at page one; you open the
middle, check, and then decide whether to go left or right.
Example
Using the same array:
Code
[5, 12, 18, 23, 45, 67, 89]
Searching for 45 using Binary Search:
• Middle element = 23 → 45 > 23 → search right half.
• New subarray = [45, 67, 89]. Middle = 67 → 45 < 67 → search left half.
• New subarray = [45]. Middle = 45 → found!
It took 3 comparisons instead of 5.
Why Binary Search is More Efficient
• Linear Search: In the worst case, you may need to check every element. For n
elements, that’s O(n) comparisons.
• Binary Search: Each step halves the search space. For n elements, that’s O(log n)
comparisons.
Example Comparison:
• For 1,000 elements:
o Linear Search worst case → 1,000 comparisons.
o Binary Search worst case → about 10 comparisons (since log₂(1000) ≈ 10).
Easy2Siksha.com
Clearly, Binary Search is much faster for large datasets.
Recursive Binary Search Algorithm
Pseudocode
Code
Algorithm BinarySearchRecursive(arr, low, high, key):
1. If low > high:
return -1 // Key not found
2. mid ← (low + high) / 2
3. If arr[mid] = key:
return mid
4. Else if key < arr[mid]:
return BinarySearchRecursive(arr, low, mid - 1, key)
5. Else:
return BinarySearchRecursive(arr, mid + 1, high, key)
End Algorithm
Example Program (C Language)
c
#include <stdio.h>
int binarySearch(int arr[], int low, int high, int key) {
if (low > high) return -1;
int mid = (low + high) / 2;
if (arr[mid] == key) return mid;
else if (key < arr[mid]) return binarySearch(arr, low, mid - 1, key);
else return binarySearch(arr, mid + 1, high, key);
}
int main() {
int arr[] = {5, 12, 18, 23, 45, 67, 89};
int n = sizeof(arr)/sizeof(arr[0]);
int key = 45;
int result = binarySearch(arr, 0, n-1, key);
if (result != -1)
printf("Element found at index %d\n", result);
else
printf("Element not found\n");
return 0;
}
This program demonstrates recursive Binary Search.
Complexity Analysis
Easy2Siksha.com
1. Linear Search
• Best Case: O(1) (element found at first position).
• Worst Case: O(n) (element at last position or not present).
2. Binary Search
• Best Case: O(1) (element found at middle).
• Worst Case: O(log n) (search space halved each time).
Why O(log n)? At each step, the array size reduces by half:
• Step 1 → n elements
• Step 2 → n/2 elements
• Step 3 → n/4 elements … until 1 element remains. Number of steps = log₂(n).
Real-Life Analogy
• Linear Search: Looking for a name in a phonebook by checking each entry one by
one.
• Binary Search: Opening the phonebook in the middle, deciding whether the name is
earlier or later, and narrowing down quickly.
Clearly, Binary Search saves time and effort.
Summary Table
Aspect
Linear Search
Binary Search
Requirement
Works on unsorted data
Requires sorted data
Best Case
O(1)
O(1)
Worst Case
O(n)
O(log n)
Efficiency
Slow for large datasets
Very fast for large datasets
Analogy
Checking each person in a queue
Searching a word in a dictionary
Final Thoughts
Binary Search is more efficient than Linear Search because it reduces the search space by
half at each step, leading to logarithmic time complexity. While Linear Search is simple and
works on unsorted data, Binary Search shines when data is sorted, making it the preferred
choice for large datasets.
Easy2Siksha.com
SECTION-D
7. (a) Briey explain the features of C++ programming language. Explain dierent
mechanism for accessing data members and member funcons in a class with examples.
(b) List the dierent types of constructors. Write a program to illustrate the use of
dierent types of constructors.
Ans: (a) Features of C++ and How We Access Data Members & Member Functions
First, what is C++ really like?
Think of C++ as a powerful upgrade over C. It not only allows normal programming, but also
introduces the concept of Object-Oriented Programming (OOP). That basically means we
can represent real-life things as objects, like a student, car, bank account etc. Each of these
objects has data and actions.
Now let’s talk about important features:
Important Features of C++
Object Oriented Programming
C++ supports concepts like:
• Classes & Objects
• Inheritance
• Polymorphism
• Encapsulation
• Abstraction
This helps us organize programs like real-life systems.
Simple but Powerful
If you know C language, C++ feels familiar. It uses similar syntax and structure, but adds
many advanced features.
Fast & Efficient
Easy2Siksha.com
C++ is used where speed matters:
games, operating systems, database engines, banking systems, etc. because it gives full
control over memory.
Platform Independent
A C++ program written once can run on different systems (with the help of compilers). So it
offers portability.
Supports OOPS + Procedural Programming
Unlike Java (pure OOP), C++ supports:
• Traditional programming (like C)
• Object oriented style
So we get the best of both worlds.
Reusability
With features like inheritance, we can reuse old classes to build new ones without rewriting
everything.
Extensible
You can easily add new features and classes according to program needs.
So these are the friendly superpowers of C++.
How Do We Access Data Members & Member Functions in a Class?
Imagine a class as a house, and data members are things inside the house (like furniture),
while member functions are the activities people do inside.
But can anyone just enter?
No! That’s where access specifiers come in.
Easy2Siksha.com
Access Specifiers
Public
Anyone can access it
Private
Only the class can access it
Protected
Accessible inside class and derived classes
Example:
class Student {
private:
int roll;
public:
void setRoll(int r) {
roll = r;
}
void display() {
cout << "Roll Number: " << roll;
}
};
Here:
• roll is private, so it cannot be accessed directly.
• We use public functions setRoll() and display() to access it.
Accessing Members Using Object
We create an object and use . operator.
Student s;
s.setRoll(10);
s.display();
Access Using Pointer to Object
We can also access members using ->
Easy2Siksha.com
Student *p;
p = &s;
p->display();
Access Using Reference
Reference works like nickname:
Student &ref = s;
ref.display();
So, accessing data members directly is normally restricted (if private), but accessing through
functions is allowed. This is called Encapsulation — protecting data and controlling access.
(b) Types of Constructors and Example Program
Let’s understand constructors in a storytelling style
Imagine when a baby is born, parents immediately give a name, birth date etc. That means
some values are set automatically at creation time.
Same happens in C++…
When an object is created, a constructor automatically runs and initializes data.
What is a Constructor?
A constructor is a special member function:
• Same name as class
• No return type (not even void)
• Called automatically
🏷 Types of Constructors
Default Constructor
A constructor with no arguments.
If you don’t write any, C++ gives an automatic one.
Easy2Siksha.com
class Demo {
public:
Demo() {
cout << "Default Constructor Called";
}
};
Parameterized Constructor
Constructor with parameters to assign values.
class Demo {
private:
int x;
public:
Demo(int a) {
x = a;
}
};
Copy Constructor
Creates new object as copy of another.
Demo(Demo &obj) {
x = obj.x;
}
Constructor Overloading
When we create multiple constructors with different parameters.
Now let’s write a clear program showing all these types together.
Program Demonstrating All Constructors
#include <iostream>
using namespace std;
class Student {
Easy2Siksha.com
int roll;
string name;
public:
// Default Constructor
Student() {
roll = 0;
name = "Unknown";
cout << "\nDefault Constructor Called";
}
// Parameterized Constructor
Student(int r, string n) {
roll = r;
name = n;
cout << "\nParameterized Constructor Called";
}
// Copy Constructor
Student(Student &s) {
roll = s.roll;
name = s.name;
cout << "\nCopy Constructor Called";
}
void display() {
cout << "\nRoll: " << roll << " Name: " << name;
}
};
int main() {
Student s1; // Default constructor
s1.display();
Student s2(101, "Rahul"); // Parameterized constructor
s2.display();
Student s3(s2); // Copy constructor
s3.display();
return 0;
}
What Happens in This Program?
Easy2Siksha.com
When s1 is created → Default constructor runs
When s2 is created → Parameterized constructor runs
When s3 is created using s2 → Copy constructor runs
This clearly shows real use of constructors.
Final Simple Summary
C++ Features
• Supports Object-Oriented Programming
• Fast and powerful
• Portable
• Supports both C style and OOP
• Allows reusability and extensibility
Accessing Class Members
• public, private, protected
• Access using:
o Object
o Pointer
o Reference
Constructors
• Automatically called when object is created
• Types:
o Default
o Parameterized
o Copy
o Overloaded
Easy2Siksha.com
8. (a) List the rules associated with operator overloading. What are the operators that
cannot be overloaded? Write a program to overload any one of the binary operators.
(b) Write a C++ program to illustrate the process of mul-level mulple inheritance
concept of C++ language.
Ans: Part (a) Operator Overloading
What is Operator Overloading?
Operator overloading allows us to redefine how operators (like +, -, *, etc.) work with user-
defined types (classes).
Imagine you create a class Complex for complex numbers. By default, the + operator
won’t know how to add two complex numbers. With operator overloading, you can teach +
to add them naturally.
Rules of Operator Overloading
1. Cannot change operator precedence or associativity.
o The rules of mathematics remain the same.
2. Cannot create new operators.
o You can only redefine existing ones.
3. At least one operand must be a user-defined type.
o You cannot overload operators for built-in types alone.
4. Cannot change the number of operands.
o Unary operators remain unary, binary remain binary.
5. Cannot change the meaning of . (dot), :: (scope resolution), sizeof, ?: (ternary), and
typeid.
o These operators are fundamental to the language and cannot be overloaded.
6. Overloading should preserve intuitive meaning.
o For example, + should represent addition-like behavior, not something
unrelated.
Operators That Cannot Be Overloaded
• :: (scope resolution)
• . (member access)
• .* (pointer-to-member access)
• ?: (ternary conditional)
• sizeof
• typeid
Example Program: Overloading the + Operator
Let’s overload the + operator for a Complex class.
Easy2Siksha.com
cpp
#include <iostream>
using namespace std;
class Complex {
int real, imag;
public:
Complex(int r = 0, int i = 0) {
real = r;
imag = i;
}
// Overload + operator
Complex operator + (const Complex& obj) {
Complex result;
result.real = real + obj.real;
result.imag = imag + obj.imag;
return result;
}
void display() {
cout << real << " + " << imag << "i" << endl;
}
};
int main() {
Complex c1(3, 4), c2(1, 2);
Complex c3 = c1 + c2; // Uses overloaded +
cout << "Result of addition: ";
c3.display();
return 0;
}
Output:
Code
Result of addition: 4 + 6i
This program shows how operator overloading makes code intuitive and natural.
Part (b) Multi-Level Multiple Inheritance
What is Inheritance?
Inheritance allows one class to acquire properties and behaviors of another.
Easy2Siksha.com
Think of it like a family tree: children inherit traits from parents, and grandchildren
inherit traits from both parents and grandparents.
Types of Inheritance in C++
1. Single Inheritance: One class inherits from another.
2. Multiple Inheritance: A class inherits from more than one base class.
3. Multi-Level Inheritance: A class inherits from another, which itself inherits from
another (like a chain).
4. Hybrid Inheritance: Combination of multiple types.
Multi-Level Multiple Inheritance
This is a combination where:
• Inheritance happens across multiple levels (grandparent → parent → child).
• A class may also inherit from multiple base classes at the same time.
Example:
• Class Person (grandparent).
• Class Employee inherits from Person.
• Class Manager inherits from Employee and also from another class Department.
Example Program
cpp
#include <iostream>
using namespace std;
// Base class
class Person {
public:
void showPerson() {
cout << "I am a Person." << endl;
}
};
// Derived class from Person (multi-level)
class Employee : public Person {
public:
void showEmployee() {
cout << "I am an Employee." << endl;
}
};
// Another base class
Easy2Siksha.com
class Department {
public:
void showDepartment() {
cout << "I belong to a Department." << endl;
}
};
// Manager inherits from Employee (multi-level) and Department (multiple)
class Manager : public Employee, public Department {
public:
void showManager() {
cout << "I am a Manager." << endl;
}
};
int main() {
Manager m;
m.showPerson(); // Inherited from Person
m.showEmployee(); // Inherited from Employee
m.showDepartment(); // Inherited from Department
m.showManager(); // Own function
return 0;
}
Output:
Code
I am a Person.
I am an Employee.
I belong to a Department.
I am a Manager.
This program beautifully illustrates multi-level multiple inheritance. The Manager class
inherits traits from both the Employee (which itself inherits from Person) and Department.
Why Are These Concepts Important?
• Operator Overloading: Makes user-defined types behave like built-in types,
improving readability and usability.
• Inheritance: Promotes code reuse, modularity, and logical hierarchy.
• Multi-Level Multiple Inheritance: Models real-world scenarios where entities inherit
traits from multiple sources across generations.
A Relatable Story
Imagine a company:
Easy2Siksha.com
• At the top, you have Person (everyone is a person).
• Then, some people are Employees (they work in the company).
• Employees belong to Departments (like HR, IT).
• Finally, some employees are Managers, who inherit qualities of being a person, an
employee, and belonging to a department.
This is exactly how multi-level multiple inheritance works in C++.
Summary Table
Concept
Key Points
Example
Operator
Overloading
Redefines operators for user-
defined types
Overloading + for Complex
numbers
Rules
Cannot change precedence,
cannot overload ::, ., sizeof, etc.
Preserves intuitive meaning
Multi-Level
Inheritance
Class inherits from another,
forming a chain
Person → Employee → Manager
Multiple
Inheritance
Class inherits from more than one
base class
Manager inherits Employee +
Department
Combined
Multi-level + multiple inheritance
Manager inherits traits from
Person, Employee, Department
Final Thoughts
Operator overloading and inheritance are two powerful features of C++. Operator
overloading makes classes behave naturally with operators, while inheritance builds logical
hierarchies and promotes code reuse. Multi-level multiple inheritance models complex real-
world relationships, showing the flexibility of C++.
“This paper has been carefully prepared for educaonal purposes. If you noce any
mistakes or have suggesons, feel free to share your feedback.”
